\section{The two-hop walk: Discovery through pull}
\label{sec:discovery.2hop}
In this section, we analyze the two-hop walk process on undirected
connected graphs, which is described by the following simple
iteration: In each round, for each node $u$, we add edge $(u,w)$
where $w$ is drawn uniformly at random from $\nei{t}{1}{v}$, where $v$
is drawn uniformly at random from $\nei{t}{1}{u}$.  The two-hop walk
yields the following pull-based resource discovery protocol.  In each
round, each node $u$ contacts a random neighbor $v$, receives the
identity of a random neighbor $w$ of $v$, and sends its identity to
$w$.  The main result of this section is that the two-hop walk process
transforms an arbitrary connected $n$-node graph to a complete graph
in $O(n \log^2 n)$ rounds with high probability.  We also establish an
$\Omega(n\log n)$ lower bound on the two-hop walk for almost all
$n$-node graphs.

\junk{
%%%%%%%%%%% BEGIN JUNK
\begin{problem}[2-hop random walk]
\label{prob:hopwalk}
Given a connected graph $G=(V,E)$, in each round, node $u$ takes a 2
hop random walk and reaches node $v$. We add edge $(u,v)$ to $G$. The
question is how many rounds it takes for $G$ to become a complete
graph.
\end{problem}


\begin{figure}[ht]
\begin{center}
  \includegraphics[width=4.5in]{./figures/randwalk.jpg}
  \caption{Simulations of two-hop random walk process \label{fig:discovery.randwalk}}
\end{center}
\end{figure}

\begin{remark}
Problem \ref{prob:triangle} and \ref{prob:hopwalk} can have the
following variation, $\forall u$, it has knowledge of neighbors within
2 hops. Can this make the processes complete faster?
\end{remark}

\begin{lemma}
\label{lem:discovery.degree}
If each node has degree at least $d$, and has at least $r$ random
edges, then in $\Theta(n\log d)$ rounds, the degree becomes
$\min\cub{n-1,\Omega(dr)}$.
\end{lemma}
\begin{proof}
First, we define $e$ to be semi-random edge if
\[\prob{e\mbox{ pointing any node }\tau | e_1,e_2,\dots} \le \frac{1}{dr}\]
In the 2-hop random walk process, each round node $u$ picks a random
neighbor, $v$, then picks a random neighbor of $v$, $w$, and adds edge
$(u,w)$. The probability that $(u,w)$ is a semi-random edge is
$s_u/n$, where $s_u$ is the lower bound on the number of semi-random
edges of $u$'s neighbors. Observe that if $(v,w)$ is a semi-random
edge of $v$, then $(u,w)$ is a semi-random edge of $u$.

In the following, we use iterative argument. At the start of iteration
$i$ ($i=1,2,\dots,\log d$), we maintain the following 2 conditions: (1)
each node has at least $r_i$ semi-random edges ($r_1 = r$); (2)
\[\prob{e\mbox{ lands on any node }\tau | e_1,e_2,\dots} \le \frac{1}{dr}\]
where $e,e_1,e_2,\dots$ are semi-random edges. And at the end of the
iteration, we argue (1) the number of semi-random edges for each node
is at least $2r_i$; (2)
\[\prob{e\mbox{ lands on any node }\tau | e_1,e_2,\dots} \le \frac{1}{dr}\]
As we can see, at the end of $(\log d)$th iteration, each node has at
least $dr$ semi-random edges. By the definition of semi-random edges,
we know these edges will point to $rd$ distinct nodes. In the
following, we will show these 2 conditions are true at the start of
the 1st round, and maintain to be true at the end of each iteration.

At the start of $i=1$ iteration, every node has $r$ turely random
edges. Set $r_1 = r$. Thus, we satisfy both conditions.

Within each iteration, we run the 2-hop random walk process for
$O(n\log n)$ rounds. In each round, the probability that a node $u$
picks a semi-random edge is at least $r_i/n$. So in $O(n)$ rounds,
$u$'s number of semi-random edges will become $2r_i$ with constant
probability. Thus, in $O(n\log n)$ rounds, with high probability
(probability goes to 1) $u$'s number of semi-random edges will
double. And from the way semi-random edges are generated, the
probability that it points to any node doesn't depend on any other
semi-random edges, i.e., we preserve condition
\[\prob{e\mbox{ lands on any node }\tau | e_1,e_2,\dots} \le \frac{1}{dr}\]
Thus, we complete our proof of this lemma.

Define $S_u$ to be the set of nodes that node $u$'s neighbors'
semi-random edges point to. Then at the start of the 1st round,
$|S_u|\ge dr$
\end{proof}

\begin{lemma}
\label{lem:discovery.star+randwalk}
If start with a star graph, the 2-hop random walk process completes in
$O(n\log^2 n)$ rounds.
\end{lemma}
\begin{proof}
First, in $O(n\log n)$ steps, every node of the star (except the
center) has $\Omega(\log n)$ random neighbors. This is simply because
for each node $u$, the probability that its 2-hop random walk goes
through the center is at least $1/n$. Split these $\Omega(\log n)$
random neighbors into $\Omega(\log n)$ sets of $r = \Omega(1)$
neighbors. Now apply Lemma \ref{lem:discovery.degree} $O(\log n)$ times, one by
one, with these $\Omega(\log n)$ sets of random neighbors, the degree
of every node will become $n-1$.
\end{proof}

\begin{lemma}
\label{lem:discovery.dumbbell+randwalk}
If start with a dumbbell graph, the 2-hop random walk process
completes in $O(n\log n)$ rounds.
\end{lemma}
\begin{proof}
Let $A$ and $B$ be complete graphs, each with $n/2$ nodes. $u\in A$
and $v\in B$, add edge $(u,v)$. Call this new graph $G$.

First we argue that in $O(n\log n)$ rounds, there are $\Omega(n)$
edges connecting $u$ (or $v$) to nodes in $B$ (or $A$). Let $k$ be the
number of edges connecting $u$ to $B$. The probability of $w\in B$
connecting to $u$ in a single round is $k/n\cdot 1/n=k/n^2$. We have
$n/2-k$ such nodes, so in $t$ rounds we expect to have $t\cdot
(n-k)\cdot k/n^2$ edges connect to $u$.
\[ t(n-k)\frac{k}{n^2} \ge 2k \Longrightarrow t\ge \frac{2n^2}{n-k}\]
Thus, in $O(n)$ rounds $k$ doubles until $k=\Omega(n)$. Therefore,
$O(n\log n)$ rounds, $u$ has $\Omega(n)$ edges connecting nodes in
$B$.

Next, we argue in $O(n\log n)$ rounds, $u$ (or $v$) connects every
nodes in $B$ (or $A$). After the first step, $u$ has $\Omega(n)$ edges
to $B$. In each round, $u$ will pick a random node in $B$ with
probability $c/n$ for some constant $c$. Like coupon collector
problem, in $O(n\log n)$ rounds, $u$ will connect every node in $B$.

Finally, we argue that $\forall w\in A$ ($w\neq u$), $w$ connects all
the nodes in $B$ in $O(n\log n)$ time. Let $k$ be the number of edges
connecting $w$ to $\cub{u}\cup B$, by the same arguement in the first
step, we showed that in $O(n\log n)$ rounds, $w$ connects to all the
nodes in $B$. And this completes the proof of this lemma.
\end{proof}
%%%%%%  END JUNK
}

\junk{
%%%%%% BEGIN JUNK
Let $G$ denote the graph, $d(u)$ denote the degree of node $u$, and
$N_i(u)$ denote the set of nodes that are at distance exactly $i$ from
$u$.  Let $\mindegree$ denote the minimum degree of $G$.  We note that
$G$, $d(u)$, and $N^i(u)$ all change with time, and are, in fact,
random variables.  For any nonnegative integer $t$, we use the
subscript $t$ to denote the random variable at the start of time $t$;
for example, $G_t$ refers to the graph at the start of round $t$.
%%%%%% END JUNK
}

\subsection{Upper bound}
As for the triangulation process, we establish the $O(n \log^2 n)$
upper bound by showing that the minimum degree of the graph increases
by a constant factor (or equals $n-1$) in $O(n \log n)$ rounds with
high probability.  For analyzing the growth in the degree of a node
$u$, we consider two overlapping cases.  The first case is when the
two-hop neighborhood of $u$ is not too large, i.e., $|\nei{t}{2}{u}| <
\md{0}/2$, and the second is when the two-hop neighborhood of $u$ is
not too small, i.e., $|\nei{t}{2}{u}| \ge \md{0}/4$.  As in the
analysis of the triangulation process, we also use the notions of
strongly and weakly tied based on how many edges connect a node to a
given set; it is more convenient to work with a different threshold.
We say that a node $v$ is {\bf {\em weakly tied}} to a set of
nodes $S$ if $v$ has less than $\md{0}/4$ edges to $S$
(i.e. $\dgi{t}{v}{S}<\md{0}/4$), and {\bf {\em strongly tied}} to $S$
if $v$ has at least $\md{0}/4$ edges to $S$ (i.e. $\dgi{t}{v}{S}
\ge\md{0}/4$).

\begin{lemma}[{\bf When the two-hop neighborhood is not too large}]
\label{lem:discovery.mingrowth-1}
There exists $T=O(n\log n)$ such that either $\abs{\nei{T}{2}{u}} \ge
\md{0}/2$ or $\dg{T}{u} \ge \min\cub{2\md{0},n-1}$ with probability at
least $1-1/n^2$.
\end{lemma}
\begin{proof}
By the definition of $\md{0}$, $\dg{0}{w} \ge \md{0}$ for all
$w$ in $\nei{0}{1}{u}$.  Let $X$ be the first round at which
$|\nei{X}{2}{u}| \ge \md{0}/2$.  We consider two cases.  If $X$ is at
most $c n \log n$ for a constant $c$ to be specified later, then the
claim of the lemma holds.  In the remainder of this proof we consider
the case where $X$ is greater than $cn \log n$; thus, for $0 \le t \le
cn\log n$, $|\nei{t}{2}{u}| <\md{0}/2$.

Consider any node $w$ in $\nei{0}{1}{u}$.  Since $\dg{0}{w} \ge
\md{0}$ and $|\nei{t}{2}{u}| <\md{0}/2$, $w$ has at least $\md{0}/2$
edges to nodes in $\nei{0}{1}{u}$.  Fix a node $v$ in
$\nei{0}{2}{u}$.  In the following, we first show that in $O(n\log n)$
rounds, $v$ is strongly tied to the neighbors of $u$ with probability
at least $1-1/n^3$.  Let $T_1$ denote the first round at which $v$ has
is strongly tied to $\nei{T_1}{1}{u}$, i.e., when $|\nei{T_1}{1}{v}
\cap \nei{T_1}{1}{u}| \ge \md{0}/4$.  We know that $v$ has at least
one neighbor, say $w_1$, in $\nei{0}{1}{u}$.  Consider any $t < T_1$.
Since $v$ is weakly tied to $\nei{0}{1}{u}$ at time $t$, $w_1$ has at
least $\md{0}/4$ neighbors in $\nei{0}{1}{u}$ which do not have an
edge to $v$ at time $t$. This implies
\[\prob{v\mbox{ connects to a node in }\nei{0}{1}{u}\mbox{ through
  }w_1\mbox{ in round $t$}} \ge \frac{1}{n}\cdot\frac{1}{4} = \frac{1}{4n}\]

\junk{
%%%%%%%% BEGIN JUNK
In $T'=16n\ln n$ rounds,
\begin{eqnarray*}
\prob{v\mbox{ connects to a node in }N^0_1(u)} &\ge& 1-\rb{1-\frac{1}{4n}}^{16n\ln n} \\
&\ge& 1-e^{-4\ln n} \\
&=& 1-\frac{1}{n^4}
\end{eqnarray*}
which means that $v$ connects to another node in $N^0_1(u)$, $w_2$, in
$T'$ rounds with probability at least $1-1/n^4$. Notice that
$w_1,w_2\in N^0_1(u)\subseteq N^{T'}_1(u)$.  Again, if $v$ does not
have at least $\mindegree/4$ neighbors in $N^{T'}_1(u)$, both $w_1$
and $w_2$ have at least $\mindegree/4$ neighbors in $N^{T'}_1(u)$ that
don't connect to $v$ yet.  So in another $T'/2$ rounds, $v$ will
connect to a new node $w_3$ in $N^{3T'/2}_1(u)$ with probability
\begin{eqnarray*}
& & 1-\prob{\cap_{i=1}^{2} \neg \cub{v\mbox{ connects to a node in }N^{T'}_1(u)\mbox{ through }w_i}} \\
&=& 1-\cap_{i=1}^{2} \prob{\neg \cub{v\mbox{ connects to a node in }N^{T'}_1(u)\mbox{ through }w_i}} \\
&\ge& 1-\frac{1}{n^{2}}\cdot\frac{1}{n^{2}} \\
&\ge& 1-\frac{1}{n^4}
\end{eqnarray*}
We can apply this argument until $v$ has at least $\mindegree/4$ edges
to $N^t_1(u)$. Total number of rounds used is bounded by
\[T'+\frac{T'}{2}+\frac{T'}{3}+\dots+\frac{T'}{\mindegree /4} \le T'\ln \mindegree\]
%%%%%%%%%%% END JUNK
}

Let $e_1$ denote the event $\cub{v\mbox{ connects to a node in
  }\nei{0}{1}{u}}$, and $X_1$ be the number of rounds for $e_1$ to
occur.  When $e_1$ occurs, let $w_2$ denote a witness for $e_1$.  We
note that $w_1,w_2\in \nei{0}{1}{u}\subseteq \nei{X_1}{1}{u}$. If $v$
is weakly tied to $\nei{X_1}{1}{u}$, both $w_1$ and $w_2$ have at
least $\md{0}/4$ neighbors in $\nei{X_1}{1}{u}$ that do not have an
edge to $v$ yet. Let $e_2$ denote the event $\cub{v\mbox{ connects to
    a node in }\nei{X_1}{1}{u}}$, and $X_2$ be the number of rounds
for $e_2$ to occur. Then $\prob{e_2} = 2\prob{e_1} \ge 1/2n$.
Similarly, we define $e_3,X_3,\dots, e_{\md{0}/4},X_{\md{0}/4}$ and
obtain $\prob{e_i} \ge i/(4n)$.  We now apply
Lemma~\ref{lem:discovery.couponcorollary} to obtain that $X_1+X_2+\ldots
X_{\md{0}/4}$ is at most $16n\ln n$ with probability at least $1 -
1/n^3$.  Thus, with probability at least $1 - |\nei{0}{2}{u}|/n^3$,
$T_1 \le 16n \ln n$.  After $T_1$ rounds, we obtain that for any $v
\in \nei{0}{2}{u}$,
\[\prob{u\mbox{ connects to }v\mbox{ in a single round}} \ge \frac{\md{0}/4}{2\md{0}}\cdot\frac{1}{n} = \frac{1}{8n}.\]
which implies that with probability at least $1 - 1/n^3$, $u$ has an
edge to every node in $\nei{0}{2}{u}$ in another $T_2 \le 24 n \ln
n$ rounds.

Let $T_3$ equal $T_1 + T_2$; we set $c$ to be at least $120\ln 2$ so
that $X > 3T_3$.  We thus have $\nei{0}{2}{u}\subseteq
\nei{T_3}{1}{u}$, $\nei{0}{3}{u}\subseteq \nei{T_3}{1}{u}\cup
\nei{T_3}{2}{u}$, and $\nei{0}{4}{u}\subseteq \nei{T_3}{1}{u}\cup
\nei{T_3}{2}{u}\cup \nei{T_3}{3}{u}$. We now repeat the above analysis
again twice and obtain that at time $T = 3T_3$, $\nei{0}{2}{u}\cup
\nei{0}{3}{u}\cup \nei{0}{4}{u}\subseteq \nei{T}{1}{u}$ with
probability at least $1-\abs{\nei{0}{2}{u}\cup \nei{0}{3}{u}\cup
  \nei{0}{4}{u}}/n^3 \ge 1-1/n^2$.  By Lemma \ref{lem:discovery.moreneighbor},
we have $\abs{\nei{T}{1}{u}}\ge \min\cub{2\md{0}, n-1}$, thus
completing the proof of the lemma.
\end{proof}

\begin{lemma}[{\bf When the two-hop neighborhood is not too small}]
\label{lem:discovery.mingrowth-2}
There exists $T=O(n\log n)$ such that either $\abs{\nei{T}{2}{u}}$ is
less than $\md{0}/4$ or $\dg{T}{u}$ is at least
$\min\cub{(1+1/8)\md{0},n-1}$, with probability at least $1-1/n^2$.
\end{lemma}
\begin{proof}
Let $X$ be the first round at which $\nei{X}{2}{u} < \md{0}/4$. We
consider two cases. If $X$ is at most $cn\log n$ for a constant $c$ to
be specified later, then the claim of the lemma holds. In the
remainder of this proof we consider the case where $X$ is greater than
$cn\log n$; thus, for $0\le t\le cn\log n$, $\abs{\nei{t}{2}{u}} \ge
  \md{0}/4$. If $v\in \nei{0}{2}{u}$ is strongly tied to $\nei{0}{1}{u}$,
then
\[\prob{u\mbox{ connects to }v\mbox{ in a single round}} \ge
\frac{\dgi{t}{v}{\nei{0}{1}{u}}}{\abs{\nei{t}{1}{u}}}\cdot
\frac{1}{n}\ge \frac{\md{0}/4}{(1+1/8)\md{0}}\cdot \frac{1}{n} =
\frac{2}{9n}\] Thus, in $T = 13.5n\ln n$ rounds, $u$ will add an edge
to $v$ with probability at least $1-1/n^3$.  If there are at least
$\md{0}/8$ nodes in $\nei{0}{2}{u}$ that are strongly tied to
$\nei{0}{1}{u}$, then $u$ will add edges to all these nodes in $T$
rounds with probability at least $1-1/n^2$.

In the remainder of this proof, we focus on the case where the number
of nodes in $\nei{0}{2}{u}$ that are strongly tied to
$\nei{0}{1}{u}$ at the start of round $0$ is less than $\md{0}/8$.  In
this case, because $\abs{\nei{t}{2}{u}}\ge \md{0}/4$, more than
$\md{0}/8$ nodes in $\nei{0}{2}{u}$ are weakly tied to
$\nei{0}{1}{u}$, and, thus, have at least $3\md{0}/4$ edges to
nodes in $\nei{0}{2}{u}\cup \nei{0}{3}{u}$.

In the following we show $u$ will connect to $\md{0}/8$ nodes in
$O(n\log n)$ rounds with probability at least $1-1/n^2$.  For any
round $t$, let $W_t$ denote the set of nodes in $\nei{t}{2}{u}$
that are weakly tied to $\nei{t}{1}{u}$.  We refer to a length-2 path
from $u$ to a node two hops away as an {\em out-path}.  Let $P_0$
denote the set of out-paths to $W_0$.  Since we have at least
$\md{0}/8$ nodes in $\nei{0}{2}{u}$ that are weakly tied to
$\nei{0}{1}{u}$, $\abs{P_0}$ is at least $\md{0} /8$ at time
$t=0$. Define $e_1=\cub{u \mbox{ picks an out-path in $P_0$ and
    connects to node }v_1\mbox{ in }\nei{0}{2}{u}}$, and $X_1$ to be
the number of rounds for $e_1$ to occur.  When $0\le t\le X_1$, for
each $w_i\in \nei{t}{1}{u}$, let $f_i$ be the number of edges from
$w_i$ to nodes in $\nei{t}{1}{u}\cup \nei{t}{2}{u}$, and $p_i$ be
the number of edges from $w_i$ to nodes in $\nei{0}{2}{u}$ that are
weakly tied to $\nei{0}{1}{u}$.
\begin{eqnarray*}
\prob{e_1} 
&=& \sum_i \frac{1}{\dg{t}{u}} \cdot \frac{p_i}{f_i} 
\;\;\;\ge\;\;\; \sum_i \frac{1}{\dg{t}{u}} \cdot \frac{p_i}{n-1} 
\;\;\;=\;\;\; \frac{\sum_i p_i}{(1+1/8)\md{0}(n-1)} \\
&=& \frac{\abs{S}}{(1+1/8)\md{0}(n-1)} 
\;\;\;\ge\;\;\; \frac{\md{0}/8}{(1+1/8)\md{0}(n-1)} 
\;\;\;\ge\;\;\; \frac{1}{9n}.
\end{eqnarray*}
After $X_1$ rounds, $u$ will pick an out-path in $P_0$ and connect
such a $v_1$.  Define $P_1$ to be a set of out-paths from $u$ to
$W_{X_1}$.  We now place a lower bound on $|P_1 \setminus P_0|$.
Since $v_1\in \nei{0}{2}{u}$ is added to $\nei{X_1}{1}{u}$, those
out-paths in $P_0$ consisting of edges from $v_1$ to nodes in
$\nei{0}{1}{u}$ are not in $P_1$. The number of out-paths we lose
because of this is at most $\md{0}/4$.  But $v_1$ also has at least
$3\md{0}/4$ edges to $\nei{0}{2}{u}\cup \nei{0}{3}{u}$. The end points
of these edges are in $\nei{X_1}{1}{u}\cup \nei{X_1}{2}{u}$. If more
than $\md{0}/8$ of them are in $\nei{X_1}{1}{u}$, then $\dg{X_1}{u}\ge
(1+1/8)\md{0}$. Now let's consider the case that less than $\md{0}/8$
such end points are in $\nei{X_1}{1}{u}$. This means the number of
edges from $v_1$ to $\nei{X_1}{2}{u}$ is at least $3\md{0}/4 -
\md{0}/4 - \md{0}/8 = 3\md{0}/8$.  Among the end points of these
edges, if more than $\md{0}/8$ of them are strongly tied to
$\nei{X_1}{1}{u}$, then the degree of $u$ will become at least
$(1+1/8)\md{0}$ in $O(n \log n)$ rounds with probability $1-1/n^2$ by
our earlier argument. If not, we know that more than $\md{0}/4$ newly
added edges are pointing to nodes that are weakly tied to
$\nei{X_1}{1}{u}$.  Thus, $\abs{P_1 \setminus P_0}$ is by at least
$\md{0}/4$. $\abs{S} \ge 2\cdot \md{0}/8$. Define $e_2=\cub{u\mbox{
    picks an out-path in $P_1$ and connects to node }v_2}$, and $X_2$
to be the number of rounds for $e_2$ to occur. During time $X_1\le
t\le X_2$, $\prob{e_2}$ is at least $2\cdot\frac{1}{9n}$.  Similarly,
we define $e_3,X_3,\dots,e_{\md{0}/8},X_{\md{0}/8}$ and derive
$\prob{e_i} \ge i/(9n)$. By Lemma \ref{lem:discovery.couponcorollary}, the
number of rounds for $\dg{t}{u}\ge (1+1/8)\md{0}$ is bounded by
\[T=X_1+X_2+\dots+X_{\md{0}/8} \le (2+1)9n\ln n = 27n\ln n\]
with probability at least $1-1/n^2$, completing the proof of this
lemma.
\end{proof}
\junk{
\begin{lemma}
\label{lem:discovery.mingrowth}
Given a connected graph $G=(V,E)$, there exists $T = O(n \log n)$ such
that $\md{T}$, the minimum degree of $G_T$ is at least
$\min\cub{(1+1/8)\md{0},n-1}$ with probability at least $1-1/n$.
\end{lemma}
\begin{proof}
For each $u$ where $\dg{0}{u} < \min\cub{(1+1/8)\md{0}, n-1}$, we analyze by the following 2 cases.

First, if $|\nei{0}{2}{u}| \ge \md{0}/2$, by Lemma
\ref{lem:discovery.mingrowth-2} we know as long as $|\nei{t}{2}{u}|\ge \md{0}/4$
for all $t\ge 0$, $\dg{T}{u} \ge\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$ where $T=O(n\log n)$. Whenever the condition is
not satisfied, we know at least $\md{0}/4$ nodes in $\nei{0}{2}{u}$
has been moved to $\nei{T}{1}{u}$, which means $\dg{T}{u}
\ge\min\cub{(1+1/4)\md{0},n-1}$.

Second, if $|\nei{0}{2}{u}| < \md{0}/2$, by Lemma
\ref{lem:discovery.mingrowth-1} we know as long as $|\nei{t}{2}{u}| < \md{0}/2$
for all $t\ge 0$, $\dg{T}{u} \ge\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$ where $T=O(n\log n)$. Whenever the condition is
not satisfied, we are back to the analysis in the first case, and the
minimum degree will become $\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$.

Combine the above 2 cases, since we at most have $n$ nodes whose
degree is between $\md{0}$ and $\min\cub{(1+1/8)\md{0},n-1}$,
the minimum degree of $G$ will become at least
$\min\cub{(1+1/8)\md{0},n-1}$ in $O(n\log n)$ rounds with
probability $1-1/n$. And this completes the proof of this lemma.
\end{proof}
}

\begin{theorem}[{\bf Upper bound for two-hop walk process}]
\label{thm:discovery.graph+randwalk}
For connected undirected graphs, the two-hop walk process completes in
$O(n\log^2 n)$ rounds with high probability.
\end{theorem}
\begin{proof}
We first show that in time $T=O(n\log n)$ time, the minimum degree of
the graph increases by a factor of $1/8$, i.e., $\md{T} \ge
\min\cub{(1+1/8)\md{0}, n-1}$. Then we can apply this argument $O(\log n)$
times, and thus, complete the proof of this theorem.

For each $u$ where $\dg{0}{u} < \min\cub{(1+1/8)\md{0}, n-1}$, we
analyze by the following 2 cases. First, if $|\nei{0}{2}{u}| \ge \md{0}/2$, by Lemma
\ref{lem:discovery.mingrowth-2} we know as long as $|\nei{t}{2}{u}|\ge \md{0}/4$
for all $t\ge 0$, $\dg{T}{u} \ge\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$ where $T=O(n\log n)$. Whenever the condition is
not satisfied, we know at least $\md{0}/4$ nodes in $\nei{0}{2}{u}$
has been moved to $\nei{T}{1}{u}$, which means $\dg{T}{u}
\ge\min\cub{(1+1/4)\md{0},n-1}$.

Second, if $|\nei{0}{2}{u}| < \md{0}/2$, by Lemma
\ref{lem:discovery.mingrowth-1} we know as long as $|\nei{t}{2}{u}| < \md{0}/2$
for all $t\ge 0$, $\dg{T}{u} \ge\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$ where $T=O(n\log n)$. Whenever the condition is
not satisfied, we are back to the analysis in the first case, and the
minimum degree will become $\min\cub{(1+1/8)\md{0},n-1}$ with
probability $1-1/n^2$.

Combine the above 2 cases, since we at most have $n$ nodes whose
degree is between $\md{0}$ and $\min\cub{(1+1/8)\md{0},n-1}$,
the minimum degree of $G$ will become at least
$\min\cub{(1+1/8)\md{0},n-1}$ in $O(n\log n)$ rounds with
probability $1-1/n$. 

Now we can apply the above argument $O(\log n)$ times, and have shown
the two-hop walk process completes in $O(n\log^2 n)$ with high
probability. 
\end{proof}

\subsection{Lower bound}
\begin{theorem}[{\bf Lower bound for two-hop walk process}]
\label{lem:discovery.hop+lower}
For any connected undirected graph $G$ that has $k \ge 1$ edges less
than the complete graph the two-hop process takes $\Omega(n \log
k)$ steps to complete with probability at least $1 - O\rb{e^{-k^{1/4}}}$.
\end{theorem}
The proof of Theorem \ref{lem:discovery.hop+lower} is essentially the same as
Theorem \ref{lem:discovery.tri+lower}, and is omitted here.
